package listbyorder.access301_400.test395;

import java.util.HashMap;

public class Solution1 {

    // 超时
    public int longestSubstring(String s, int k) {
        if (k <= 1) return s.length();
        int len = s.length();
        char[] chars = s.toCharArray();
        int[] temp = new int[26];
        for (char c : chars) {
            temp[c - 'a']++;
        }
        HashMap<String, Integer> map = new HashMap<>();
        return getAns(chars, temp, k, 0, len - 1, map);
    }

    private int getAns(char[] chars, int[] temp, int k, int l, int r, HashMap<String, Integer> map) {
        if (r - l + 1 < k) return 0;
        String key = l + "@" + r;
        if (map.containsKey(key)) return map.get(key);
        int res = r - l + 1;
        for (int i = l; i <= r; i++) {
            char c = chars[i];
            if (temp[c - 'a'] == 0 || temp[c - 'a'] >= k) continue;
            // 左边缩一个
            temp[chars[l] - 'a']--;
            int left = getAns(chars, temp, k, l + 1, r, map);
            temp[chars[l] - 'a']++;
            // 右边缩一个
            temp[chars[r] - 'a']--;
            int right = getAns(chars, temp, k, l, r - 1, map);
            temp[chars[r] - 'a']++;
            res = Math.max(left, right);
        }
        map.put(key, res);
        return res;
    }
}
